106. 从中序与后序遍历序列构造二叉树

Similar Question

leading to the advanced question

Solution Tips

方案一: 递归

var buildTree = function(inorder, postorder) {
    // 后序遍历: 左右中
    // 中序遍历: 左中右

    // 最关键的一点就是, 中节点的左边是其左子树的遍历结果, 中节点的右边是其右子树的遍历结果
    // 和前序遍历的 case 几乎一样, 只是找中间节点的方式不同而已
    if (!inorder.length || !postorder.length) return null;

    const postorderRoot = postorder[postorder.length - 1];
    const inorderRootIndex = inorder.indexOf(postorderRoot);
    const leftSubTreeCount = inorderRootIndex;

    const node = new TreeNode(postorderRoot);
    // 递归的构造左子节点
    node.left = buildTree(inorder.slice(0, leftSubTreeCount), postorder.slice(0, inorderRootIndex));
    // 递归的构造右子节点
    node.right = buildTree(inorder.slice(leftSubTreeCount + 1), postorder.slice(inorderRootIndex, postorder.length - 1))

    return node;
};